Masala #0096

Adizda [1,…,N] sonlar ketma-ketligi mavjud. U bu sonlarning barcha permutatsiyasini leksikografik o’sish tartibida qog’ozga yozib oldi va ularni ketma-ketligi bo’yicha raqamlab chiqdi. Masalan N=3 uchun jami 6 ta permutatsiya bor va ular quyidagilar:

Adiz bu permutatsiyalar orasidan ixtiyoriy birini tanlab oldi va uni yodida saqladi. Bir necha kundan so’ng u o’zi tanlagan permutatsiyani qog’ozga yozmoqchi bo’lganida bildiki tanlagan permutatsiyasidagi ba’zi qiymatlar yodidan ko’tarilgan, qog’ozga yozish jarayonida u yodidan ko’tarilgan qiymatlar o’rniga 0 qiymatini yozdi. Shundan so’ng uni quyidagicha savol qiziqtirib qoldi, u tanlagan permutatsiya qog’ozdagi qaysi qatorlar bo’lishi mumkin.

INPUT.TXT kirish faylining dastlabki satrida bitta butun son, N(1 ≤ N ≤ 3*10⁵) permutatsiyadagi elementlar soni. Keyingi qatorda N ta butun son, Adizning yodida saqlagan permutatsiyasi.

OUTPUT.TXT chiqish faylida bitta butun son, Adiz yodida saqlagan permutatsiya mos kelishi mumkin bo’lgan qog’ozdagi qatorlarning qiymatlari yig’indisini 10⁹+7 ga bo’lgandagi qiymatini chop eting.